public class HashBuck2<K,V> {
    //节点结构
    public static class Node<K,V>{
        public K key;
        public V val;
        public Node<K,V> next;

        public Node(K key,V val){
            this.key=key;
            this.val=val;
        }
    }
    //节点类型的链表
    public Node<K,V>[] array = (Node<K, V>[]) new Node[10];
    //当前存放元素的个数
    public int usedSize;
    //默认负载因子
    private static final double DEFAULT_LOAD_FACTOR = 0.75;

    //存(尾插法)
    public void putLast(K key,V val){
        //哈希函数
        int hash = key.hashCode();
        int index=hash % array.length;
        Node<K,V> node = array[index];
        node.next = null;
        //遍历哈希表该下标对应的链表确定有否有一样的关键字(不判断最后一个元素,减少尾插法的循环)(一样:替换,不一样:尾插法)
        Node<K,V> cur = array[index];
        if(cur==null){
            array[index] = node;
        }else{
            while(cur.next!=null){
                if(cur.key.equals(key)){
                    cur.val=val;
                    return;
                }
                cur=cur.next;
            }
            //单独判断最后一个元素是否关键字一样(一样:替换,不一样:尾插法)
            if(cur.key.equals(key)){
                cur.val=val;
            }else{
                cur.next=node;
            }
        }
        usedSize++;
        //检查哈希表是否超过负载因子;
        if(LoadFactor() >= DEFAULT_LOAD_FACTOR){
            resizeLast();
        }
    }
    //存(头插法)
    public void putFirst(K key,V val){
        Node<K,V> node = new Node<>(key,val);
        node.next = null;
        //哈希函数
        int hash = key.hashCode();
        int index=hash % array.length;
        //遍历哈希表该下标对应的链表确定有否有一样的关键字(一样:替换,不一样:头插法)
        Node<K,V> cur = array[index];
        while(cur!=null){
            if(cur.key.equals(key)){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        node.next=array[index];
        array[index]=node;
        usedSize++;
        //检查哈希表是否超过负载因子,超过时扩容;
        if(LoadFactor() >= DEFAULT_LOAD_FACTOR){
            resizeFirst();
        }
    }
    //计算当前负载因子
    private  double LoadFactor(){
        return usedSize*1.0/array.length;
    }
    //扩容(注意需要将哈希表每个元素重新哈希到哈希表中(哈希函数改变了))
    private void resizeFirst(){
        Node<K,V>[] temp = (Node<K,V>[]) new Node[2*array.length];
        //遍历原来的哈希表
        for (int i = 0; i < array.length; i++) {
            Node<K,V> cur = array[i];
            //头插法
            while(cur!=null){
                Node<K,V> curNext = cur.next;
                int index = cur.key.hashCode() % temp.length;
                cur.next = temp[index];
                temp[index] = cur;
                cur = curNext;
            }
        }
        array = temp;
    }
    private void resizeLast(){
        Node<K,V>[] temp = (Node<K,V>[]) new Node[2*array.length];
        //遍历原来的哈希表
        for (int i = 0; i < array.length; i++) {
            Node<K,V> cur1 = array[i];
            //尾插法
            while(cur1!=null){
                Node<K,V> curNext = cur1.next;
                int index = cur1.key.hashCode() % temp.length;
                Node<K,V> cur2 = temp[index];
                if(cur2==null){
                    temp[index] = cur1;
                    cur1.next=null;
                }else{
                    while(cur2.next!=null){
                        cur2 = cur2.next;
                    }
                    cur2.next=cur1;
                    cur1.next=null;
                }
                cur1 = curNext;
            }
        }
        array = temp;
    }
    //通过关键字获取值
    public V get(K key){
        int index = key.hashCode() % array.length;
        Node<K,V> cur = array[index];
        while(cur!=null){
            if(cur.key.equals(key)){
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}
